/**
 * Created by fangcailiang on 16/6/16.
 */

/*
 一段楼梯共n级台阶，每次只能走一级，或两级，问共有多少种走法？列出n=10时的所有走法。
 */

/**
 * 递归算法
 * 使用该算法时我们发现 有很多项被重复计算如 f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3)
 * f(n-2) 就需要重复计算
 */
function plt1(n){
    if(n == 1 || 2 == n){
        return n;
    }

    return plt1(n - 1) + plt1(n -2);
}

function memorize(fun){
    var cache = {};
    return function(){
        // 将参数转换为字符串, 并将其用作缓存的键
        var key = arguments.length + Array.prototype.join.call(arguments, ",");
        if(!(key in cache)){
            cache[key] = fun.apply(this, arguments);
        }
        return cache[key];
    };
}

//console.log(plt1(50)); // 已经要费很久时间才能计算出来

//var newPlt1 = memorize(plt1);
//console.log(newPlt1(20));

// 通过 memorize 让 plt1 方法具有缓存的功能和plt2一样,但实现的更优雅
plt1 = memorize(plt1);
console.log(plt1(50));

/**
 * 使用递归算法时我们发现 有很多项被重复计算如 f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3)
 * f(n-2) 就需要重复计算
 * 备忘录算法，就是将已经计算过的数缓存起来，从而提高效率
 * @param n
 * @returns {*}
 */

function count(n, tmpArray){
    if(!tmpArray[n]){
        tmpArray[n] = count(n-1, tmpArray) + count(n-2, tmpArray);
    }
    return tmpArray[n];
}

function plt2(n){
    if(n == 1 || 2 == n){
        return n;
    }
    var tmpArray = new Array(n+1);
    tmpArray[1] = 1;
    tmpArray[2] = 2;
    return count(n, tmpArray);
}



//console.log(plt2(50)); //

/**
 * 递归有一个致命的问题就是就是会出现栈溢出，当 n = 15000时基本就会栈溢出了
 * 而且递归需要出栈入栈，性能稍低，所以我们采用循环的方式时间空间复杂度不变，不会出现栈溢出
 * 线性规划法
 * @param n
 * @returns {*}
 */
function plt3(n){
    if(n == 1 || 2 == n){
        return n;
    }
    var tmpArray = new Array(n+1);
    tmpArray[1] = 1;
    tmpArray[2] = 2;
    for(var i=3; i<=n; i++){
        tmpArray[i] = tmpArray[i-1] + tmpArray[i-2];
    }
    return tmpArray[n];
}

//console.log(plt3(10000)); //


/**
 * 线性规划法的问题是需要开辟一个数组，当n较大时，浪费内存空间，空间复杂度为 O(n)
 * 所以我们进一步优化将空间复杂度降低为 O(1)
 * @param n
 * @returns {*}
 */
function plt4(n){
    if(n == 1 || 2 == n){
        return n;
    }
    var b = 2;
    var a = 1;
    var tmp = 0;
    for(var i=3; i<=n; i++){
        tmp = a + b;
        a = b;
        b = tmp;
    }
    return tmp;
}

//console.log(plt4(1000)); //

// plt5 数学公式